﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using Satire.Common;

namespace Satire.Lexer
{
    public enum StateAction { PUSH = 2, POP = 3, ACCEPT = 5, IGNORE = 4, ERROR = 1, NULL = 0}
 

    internal class NfaState
    {
        internal NfaState(int stateNo)
        {
             _chars = null;
            _edge1 = null;
            _edge2 = null;
            _stateNo = stateNo;
            _closure = null;
            _action = StateAction.NULL;
            _operand = 0;
        }
        internal void MakeEdges(int[] chars, NfaState s1, NfaState s2)
        {
            _chars = chars;
            _edge1 = s1;
            _edge2 = s2;
        }
        internal void MakeEdges(NfaState s1, NfaState s2)
        {
            _edge1 = s1;
            _edge2 = s2;
        }
        internal void MakeEdges(NfaState s1)
        {
            _edge1 = s1;
        }
        internal void MakeEdges(int[] chars, NfaState s1)
        {
            _chars = chars;
            _edge1 = s1;
        }
        internal void SetAction(StateAction action, int operand)
        {
            _action = action;
            _operand = operand;
        }
        internal StateAction Action { get { return _action; } }
        internal int Operand { get { return _operand; } }
        internal int EdgeCount
        {
            get
            {
                if (_edge2 != null)
                {
                    return 2;
                }
                return 1;
            }
        }
        internal bool EdgeNull(int i) 
        {
            if (i == 0)
            {
                if (_edge1 != null) { if (_chars == null) { return true; } }
                return false;
            }
            if (i == 1)
            {
                if (_edge2 != null) { return true; }
                return false;
            }
            return false;
        }
        internal int EdgeState(int i)
        {
            if (i == 0)
            {
                if (_edge1 != null) { return _edge1._stateNo; }
                return -1;
            }
            if (i == 1)
            {
                if (_edge2 != null) { return _edge2._stateNo; }
                return -1;
            }
            return -1;
        }
        internal int[] Chars { get { return _chars; } }
        internal void InitializeClosure()
        {
            _closure = new DynamicArray<int>(0, DefaultCapacity, DefaultDelta);
            _closure.Add(_stateNo);
            for (int i = 0; i < EdgeCount; i++)
            {
                if (EdgeNull(i))
                {
                    _closure.AddInSequence(EdgeState(i), false);
                }
            }
  
        }
        internal bool NextClosure(List<NfaState> states)
        {
            int i = 0;
            int len = _closure.Length;
            while (i < _closure.Length)
            {
                _closure.Union(states[_closure[i]].ClosureArray);
                i++;
            }
            if (_closure.Length != len) { return true; }
            return false;
        }
        internal DynamicArray<int> ClosureArray { get { return _closure; } set { _closure = value; } }
        internal const int DefaultCapacity = 5;
        internal const int DefaultDelta = 5;
        #region Private
        private StateAction _action;
        private int _operand;
        private int[] _chars;
        private NfaState _edge1;
        private NfaState _edge2;
        private int _stateNo;
        private DynamicArray<int> _closure;
        #endregion
    }

    public class NfaSegment 
    {
        internal NfaSegment(NfaBuilder builder, NfaState nfaStart, NfaState nfaEnd)
        {
            _builder = builder;
            _start = nfaStart;
            _end = nfaEnd;
        }
        public NfaSegment Concat(NfaSegment seg)
        {
            _end.MakeEdges(seg._start);
            return new NfaSegment(_builder, _start, seg._end);
        }
        public NfaSegment Or(NfaSegment seg)
        {
            NfaState s1 = _builder.NewState();
            NfaState s2 = _builder.NewState();

            s1.MakeEdges(_start, seg._start);
            _end.MakeEdges(s2);
            seg._end.MakeEdges(s2);

            return new NfaSegment(_builder, s1, s2);
        }
        public NfaSegment Optional()
        {
            NfaState s1 = _builder.NewState();

            s1.MakeEdges(_start, _end);
            return new NfaSegment(_builder, s1, _end);
        }
        public NfaSegment Closure()
        {
            NfaState s1 = _builder.NewState();
            NfaState s2 = _builder.NewState();

            s1.MakeEdges(_start, s2);
            _end.MakeEdges(_start, s2);
            return new NfaSegment(_builder, s1, s2);
        }
        public NfaSegment ClosurePlus()
        {
            NfaState s1 = _builder.NewState();
 
            _end.MakeEdges(_start, s1);
            return new NfaSegment(_builder, _start, s1);
        }
        internal NfaState StartState
        {
            get { return _start; }
        }
        internal NfaState EndState
        {
            get { return _end; }
        }
        #region private
        private NfaBuilder _builder;
        private NfaState _start;
        private NfaState _end;
        #endregion
    }

    public class NfaBuilder
    {
        public NfaBuilder()
        {
        }
        public NfaSegment CreateSegment(int[] chars)
        {
            NfaState s1 = NewState();
            NfaState s2 = NewState();
            s1.MakeEdges(chars, s2);
            return new NfaSegment(this, s1, s2);
        }
        public int AddToken(int space, NfaSegment seg, StateAction action, int operand)
        {
            seg.EndState.SetAction(action, operand);
            _spaces[space].Add(seg);
            return  _spaces[space].Count - 1;
        }
        public int CreateSpace(int seg)
        {
            _spaces.Add(new List<NfaSegment>());
            return _spaces.Count - 1;
        }
        public Nfa GenerateNfa()
        {
            _generateClosure();
            return new Nfa(_nfaList, _spaces);
        }
        internal NfaState NewState()
        {
            NfaState ns = new NfaState(_nfaList.Count);
            _nfaList.Add(ns);
            return ns;
        }
        #region private
        private void _generateClosure()
        {
              

            // initialize closure sets
            for (int i = 0; i < _nfaList.Count; i++)
            {
                NfaState nfas = _nfaList[i];
                nfas.InitializeClosure();
            }

            bool hasChanged = true;
            while (hasChanged)
            {
                hasChanged = false;
                for (int i = 0; i < _nfaList.Count; i++)
                {
                    if (_nfaList[i].NextClosure(_nfaList)) { hasChanged = true; }
                }
            }
        }
        private List<NfaState> _nfaList = new List<NfaState>();
        private List<List<NfaSegment>> _spaces = new List<List<NfaSegment>>();
        #endregion
    }

    public class Nfa
    {
        internal Nfa(List<NfaState> nfaList, List<List<NfaSegment>> spaces)
        {
            _nfaList = nfaList;
            _spaces = spaces;
        }

        public int SpaceCount { get { return _spaces.Count; } }
        public void StartSet(int space, DynamicArray<int> set)
        {
            List<NfaSegment> nfaSegs = _spaces[space];
            for (int i = 0; i < nfaSegs.Count; i++)
            {
                set.Union(nfaSegs[i].StartState.ClosureArray);
            }
        }
        public void EdgesForSet(DynamicArray<int> set, DynamicArray<int> edges)
        {
            for (int i = 0; i < set.Length; i++)
            {
                edges.Union(_nfaList[i].Chars);
            }
        }
        public void TransitionOnEdge(int edge, DynamicArray<int> set, DynamicArray<int> toSet, ref StateAction action, ref int operand)
        {
            for (int i = 0; i < set.Length; i++)
            {
                NfaState s = _nfaList[i];
                if (s.Chars != null)
                {
                    if (Array.BinarySearch<int>(s.Chars, edge) >= 0)
                    {
                        toSet.AddInSequence(s.EdgeState(0), false);
                        action = StateAction.NULL;
                        operand = 0;
                        NfaState ts = _nfaList[s.EdgeState(0)];
                        if ((int)ts.Action > (int)action)
                        {
                            action = ts.Action;
                            operand = ts.Operand;
                        }
                        else
                        {
                            if (ts.Action == action)
                            {
                                if (ts.Operand > operand) { operand = ts.Operand; }
                            }
                        }
                    }
                }
            }
        }

        #region private
        private List<NfaState> _nfaList;
        private List<List<NfaSegment>> _spaces;
        #endregion
    }

}
